from typing import List

from sortedcontainers import SortedList


class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])

        def near(x, y):
            """计算相邻的座位"""
            res = []
            if x > 0 and y > 0:
                res.append((x - 1, y - 1))
            if x > 0 and y < n - 1:
                res.append((x - 1, y + 1))
            if y > 0:
                res.append((x, y - 1))
            if y < n - 1:
                res.append((x, y + 1))
            if x < m - 1 and y > 0:
                res.append((x + 1, y - 1))
            if x < m - 1 and y < n - 1:
                res.append((x + 1, y + 1))
            return res

        # 计算每一个座位安排人之后的影响座位数
        choose_idx = {}
        choose_lst = SortedList()
        for i1 in range(m):
            for j1 in range(n):
                if seats[i1][j1] == ".":
                    affect = 0
                    for i2, j2 in near(i1, j1):
                        if seats[i2][j2] == ".":
                            affect += 1
                    choose_idx[(i1, j1)] = affect
                    choose_lst.add((affect, i1, j1))

        # 贪心策略：每一次都选择对周围影响最少的
        ans = 0
        while choose_lst:
            print(choose_lst)
            affect, i1, j1 = choose_lst.pop(0)
            choose_idx.pop((i1, j1))
            ans += 1
            for i2, j2 in near(i1, j1):
                if (i2, j2) in choose_idx:
                    choose_lst.remove((choose_idx[(i2, j2)], i2, j2))
                    choose_idx.pop((i2, j2))
                    for i3, j3 in near(i2, j2):
                        if (i3, j3) in choose_idx:
                            choose_lst.remove((choose_idx[(i3, j3)], i3, j3))
                            choose_idx[(i3, j3)] -= 1
                            choose_lst.add((choose_idx[(i3, j3)], i3, j3))
        return ans


if __name__ == "__main__":
    # 4
    print(Solution().maxStudents(seats=[["#", ".", "#", "#", ".", "#"],
                                        [".", "#", "#", "#", "#", "."],
                                        ["#", ".", "#", "#", ".", "#"]]))

    # 3
    print(Solution().maxStudents(seats=[[".", "#"],
                                        ["#", "#"],
                                        ["#", "."],
                                        ["#", "#"],
                                        [".", "#"]]))

    # 10
    print(Solution().maxStudents(seats=[["#", ".", ".", ".", "#"],
                                        [".", "#", ".", "#", "."],
                                        [".", ".", "#", ".", "."],
                                        [".", "#", ".", "#", "."],
                                        ["#", ".", ".", ".", "#"]]))

    # 测试用例53/55 : 9
    print(Solution().maxStudents(seats=[["#", "#", "#", ".", "#"],
                                        [".", ".", "#", ".", "."],
                                        ["#", ".", "#", ".", "#"],
                                        [".", ".", ".", ".", "."],
                                        [".", ".", ".", "#", "."]]))
